package xyz.scootaloo.oj.leetcode

import cn.hutool.core.lang.Console
import org.junit.Test

/**
 * @author flutterdash@qq.com
 * @since 2021/4/30 22:59
 */
class P56 {

    fun merge(intervals: Array<IntArray>): Array<IntArray> {
        if (intervals.size <= 1) {
            return intervals
        }

        intervals.sortBy { interval -> interval[0] }

        var pos = 0
        val size = intervals.size
        var open = false  // 0:未打开  1:收集中 2:闭合

        val res = ArrayList<IntArray>()
        while (pos < size) {
            val interval = intervals[pos]
            if (open) {
                if (interval[0] <= res.last()[1]) {
                    if (interval[1] > res.last()[1])
                        res.last()[1] = interval[1]
                } else {
                    open = false
                    pos--
                }
            } else {
                res.add(intArrayOf(interval[0], interval[1]))
                open = true // 标记为打开状态
            }
            pos++
        }

        if (!open) {
            val interval = intervals[size - 1]
            res.add(intArrayOf(interval[0], interval[1]))
        }

        return res.toArray(Array(0) { IntArray(0) })
    }

    @Test
    fun test0() {
        val input = arrayOf(
            intArrayOf(1, 3),
            intArrayOf(2, 6),
            intArrayOf(8,  10),
            intArrayOf(15, 18)
        )
        val res = merge(input)
        Console.log(res)
    }

    @Test
    fun test1() {
        val input = arrayOf(
            intArrayOf(1, 4),
            intArrayOf(4, 5),
        )
        val res = merge(input)
        Console.log(res)
    }

}
